package hot100;

import org.junit.Test;

public class FindKthLargest {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        heapSort(nums);
        return nums[n - k];
    }

    private void heapSort(int[] nums) {
        int n = nums.length;
        buildHeap(nums);
        for (int i = n - 1; i > 0; i--) {
            swap(nums,0,i);
            heapify(nums,i,0);
        }
    }

    private void buildHeap(int[] nums) {
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(nums,n,i);
        }
    }

    private void heapify(int[] nums, int end, int start) {
        int largest = start;
        int left = start * 2 + 1;
        int right = start * 2 + 2;

        if (left < end && nums[left] > nums[largest]) largest = left;
        if (right < end && nums[right] > nums[largest]) largest = right;

        if (largest != start) {
            swap(nums,start,largest);
            heapify(nums,end,largest);
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    @Test
    public void test() {
        int[] ints = {3, 2, 1, 5, 6, 4};
        int res = findKthLargest(ints, 2);
        System.out.println(res);
    }
}
